package mo.tags.greedy;

public class L738 {

    public int monotoneIncreasingDigits(int n) {
        if (n < 10) {
            return n;
        }
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int i = 0;
        int len = s.length();
        for (; i < len - 1; i++) {
            if (chars[i] > chars[i+1]) {
                break;
            }
        }
        if (i == len - 1) {
            return n;
        }
        while (i - 1 >= 0 && chars[i] == chars[i-1]) {
            i--;
        }
        chars[i] = (char) (chars[i] - 1);
        i++;
        while (i < len) {
            chars[i] = '9';
            i++;
        }
        return Integer.parseInt(String.valueOf(chars));
    }


    public static void main(String[] args) {
        L738 test = new L738();
        System.out.println(Integer.parseInt("0999"));
        System.out.println(test.monotoneIncreasingDigits(1000));
    }
}
